package arithmetic.demo23;

import java.util.*;

/**
 * 动态规划：含义dp + 分类讨论 + 整合化归 ： 完全背包问题
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt(), maxV = in.nextInt();
        int[] V = new int[len + 1], W = new int[len + 1];

        // 输入
        for (int i  = 1 ; i <= len; i++ ) {
            V[i] = in.nextInt();
            W[i] = in.nextInt();
        }

        // 创建dp
        int[][] dp = new int[len + 1][maxV + 1];

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= maxV; j++) {
                // 首先继承前面的
                dp[i][j] = dp[i - 1][j];

                // 开始判断当前要的情况
                int index = j - V[i];
                if (index >= 0 ) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][index] + W[i]);
                }
            }
        }

        System.out.println(dp[len][maxV]);



        // 创建dp
        dp = new int[len + 1][maxV + 1];

        // 初始化
        for (int j  = 1 ; j <= maxV; j++) {
            dp[0][j] = -1;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= maxV; j++) {
                // 首先继承前面的
                dp[i][j] = dp[i - 1][j];

                // 开始判断当前要的情况
                int index = j - V[i];
                if (index >= 0 && dp[i][index] != -1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][index] + W[i]);
                } 

            }
        }

        System.out.println(dp[len][maxV] == -1 ? 0 : dp[len][maxV]);

    }
}